home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / xarchie-2.0.9 / regex.c < prev    next >
C/C++ Source or Header  |  1995-06-18  |  16KB  |  688 lines
  1. /*
  2.  * These routines are BSD regex(3)/ed(1) compatible regular-expression
  3.  * routines written by Ozan S. Yigit, Computer Science, York University.
  4.  * Parts of the code that are not needed by Prospero have been removed,
  5.  * but most of the accompanying information has been left intact. 
  6.  * This file is to be included on those operating systems that do not
  7.  * support re_comp and re_exec.
  8.  */
  9.  
  10. /*
  11.  * regex - Regular expression pattern matching
  12.  *         and replacement
  13.  *
  14.  * by:  Ozan S. Yigit (oz@nexus.yorku.ca)
  15.  *    Dept. of Computing Services
  16.  *      York University
  17.  *
  18.  * These routines are the PUBLIC DOMAIN equivalents 
  19.  * of regex routines as found in 4.nBSD UN*X, with minor
  20.  * extensions.
  21.  *
  22.  * Modification history:
  23.  *
  24.  * Log:    regex.c,v
  25.  * Revision 1.3  89/04/01  14:18:09  oz
  26.  * Change all references to a dfa: this is actually an nfa.
  27.  * 
  28.  * Revision 1.2  88/08/28  15:36:04  oz
  29.  * Use a complement bitmap to represent NCL.
  30.  * This removes the need to have seperate 
  31.  * code in the pmatch case block - it is 
  32.  * just CCL code now.
  33.  * 
  34.  * Use the actual CCL code in the CLO
  35.  * section of pmatch. No need for a recursive
  36.  * pmatch call.
  37.  * 
  38.  * Use a bitmap table to set char bits in an
  39.  * 8-bit chunk.
  40.  * 
  41.  * Routines:
  42.  *      re_comp:        compile a regular expression into
  43.  *                      a NFA.
  44.  *
  45.  *            char *re_comp(s)
  46.  *            char *s;
  47.  *
  48.  *      re_exec:        execute the NFA to match a pattern.
  49.  *
  50.  *            int re_exec(s)
  51.  *            char *s;
  52.  *
  53.  * Regular Expressions:
  54.  *
  55.  *      [1]     char    matches itself, unless it is a special
  56.  *                      character (metachar): . \ [ ] * + ^ $
  57.  *
  58.  *      [2]     .       matches any character.
  59.  *
  60.  *      [3]     \       matches the character following it, except
  61.  *            when followed by a left or right round bracket,
  62.  *            a digit 1 to 9 or a left or right angle bracket. 
  63.  *            (see [7], [8] and [9])
  64.  *            It is used as an escape character for all 
  65.  *            other meta-characters, and itself. When used
  66.  *            in a set ([4]), it is treated as an ordinary
  67.  *            character.
  68.  *
  69.  *      [4]     [set]   matches one of the characters in the set.
  70.  *                      If the first character in the set is "^",
  71.  *                      it matches a character NOT in the set, i.e. 
  72.  *            complements the set. A shorthand S-E is 
  73.  *            used to specify a set of characters S upto 
  74.  *            E, inclusive. The special characters "]" and 
  75.  *            "-" have no special meaning if they appear 
  76.  *            as the first chars in the set.
  77.  *                      examples:        match:
  78.  *
  79.  *                              [a-z]    any lowercase alpha
  80.  *
  81.  *                              [^]-]    any char except ] and -
  82.  *
  83.  *                              [^A-Z]   any char except uppercase
  84.  *                                       alpha
  85.  *
  86.  *                              [a-zA-Z] any alpha
  87.  *
  88.  *      [5]     *       any regular expression form [1] to [4], followed by
  89.  *                      closure char (*) matches zero or more matches of
  90.  *                      that form.
  91.  *
  92.  *      [6]     +       same as [5], except it matches one or more.
  93.  *
  94.  *      [7]             a regular expression in the form [1] to [10], enclosed
  95.  *                      as \(form\) matches what form matches. The enclosure
  96.  *                      creates a set of tags, used for [8] and for
  97.  *                      pattern substution. The tagged forms are numbered
  98.  *            starting from 1.
  99.  *
  100.  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
  101.  *                      previously tagged regular expression ([7]) matched.
  102.  *
  103.  *    [9]    \<    a regular expression starting with a \< construct
  104.  *        \>    and/or ending with a \> construct, restricts the
  105.  *            pattern matching to the beginning of a word, and/or
  106.  *            the end of a word. A word is defined to be a character
  107.  *            string beginning and/or ending with the characters
  108.  *            A-Z a-z 0-9 and _. It must also be preceded and/or
  109.  *            followed by any character outside those mentioned.
  110.  *
  111.  *      [10]            a composite regular expression xy where x and y
  112.  *                      are in the form [1] to [10] matches the longest
  113.  *                      match of x followed by a match for y.
  114.  *
  115.  *      [11]    ^    a regular expression starting with a ^ character
  116.  *        $    and/or ending with a $ character, restricts the
  117.  *                      pattern matching to the beginning of the line,
  118.  *                      or the end of line. [anchors] Elsewhere in the
  119.  *            pattern, ^ and $ are treated as ordinary characters.
  120.  *
  121.  *
  122.  * Acknowledgements:
  123.  *
  124.  *    HCR's Hugh Redelmeier has been most helpful in various
  125.  *    stages of development. He convinced me to include BOW
  126.  *    and EOW constructs, originally invented by Rob Pike at
  127.  *    the University of Toronto.
  128.  *
  129.  * References:
  130.  *              Software tools            Kernighan & Plauger
  131.  *              Software tools in Pascal        Kernighan & Plauger
  132.  *              Grep [rsx-11 C dist]            David Conroy
  133.  *        ed - text editor        Un*x Programmer's Manual
  134.  *        Advanced editing on Un*x    B. W. Kernighan
  135.  *        regexp routines            Henry Spencer
  136.  *
  137.  * Notes:
  138.  *
  139.  *    This implementation uses a bit-set representation for character
  140.  *    classes for speed and compactness. Each character is represented 
  141.  *    by one bit in a 128-bit block. Thus, CCL always takes a 
  142.  *    constant 16 bytes in the internal nfa, and re_exec does a single
  143.  *    bit comparison to locate the character in the set.
  144.  *
  145.  * Examples:
  146.  *
  147.  *    pattern:    foo*.*
  148.  *    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
  149.  *    matches:    fo foo fooo foobar fobar foxx ...
  150.  *
  151.  *    pattern:    fo[ob]a[rz]    
  152.  *    compile:    CHR f CHR o CCL bitset CHR a CCL bitset END
  153.  *    matches:    fobar fooar fobaz fooaz
  154.  *
  155.  *    pattern:    foo\\+
  156.  *    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
  157.  *    matches:    foo\ foo\\ foo\\\  ...
  158.  *
  159.  *    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
  160.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
  161.  *    matches:    foo1foo foo2foo foo3foo
  162.  *
  163.  *    pattern:    \(fo.*\)-\1
  164.  *    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  165.  *    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
  166.  * 
  167.  */
  168.  
  169. #define MAXNFA  1024
  170. #define MAXTAG  10
  171.  
  172. #define OKP     1
  173. #define NOP     0
  174.  
  175. #define CHR     1
  176. #define ANY     2
  177. #define CCL     3
  178. #define BOL     4
  179. #define EOL     5
  180. #define BOT     6
  181. #define EOT     7
  182. #define BOW    8
  183. #define EOW    9
  184. #define REF     10
  185. #define CLO     11
  186.  
  187. #define END     0
  188.  
  189. /*
  190.  * The following defines are not meant
  191.  * to be changeable. They are for readability
  192.  * only.
  193.  *
  194.  */
  195. #define MAXCHR    128
  196. #define CHRBIT    8
  197. #define BITBLK    MAXCHR/CHRBIT
  198. #define BLKIND    0170
  199. #define BITIND    07
  200.  
  201. #define ASCIIB    0177
  202.  
  203. typedef /*unsigned*/ char CHAR;
  204.  
  205. static int  tagstk[MAXTAG];             /* subpat tag stack..*/
  206. static CHAR nfa[MAXNFA];        /* automaton..       */
  207. static int  sta = NOP;                   /* status of lastpat */
  208.  
  209. static CHAR bittab[BITBLK];        /* bit table for CCL */
  210.                     /* pre-set bits...   */
  211. static CHAR bitarr[] = {1,2,4,8,16,32,64,128};
  212.  
  213. static int internal_error;
  214.  
  215. static void
  216. chset(c)
  217. register CHAR c;
  218. {
  219.     bittab[((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND];
  220. }
  221.  
  222. #define badpat(x)    return (*nfa = END, x)
  223. #define store(x)    *mp++ = x
  224.  
  225. char *     
  226. re_comp(pat)
  227. char *pat;
  228. {
  229.     register char *p;               /* pattern pointer   */
  230.     register CHAR *mp = nfa;        /* nfa pointer       */
  231.     register CHAR *lp;              /* saved pointer..   */
  232.     register CHAR *sp = nfa;        /* another one..     */
  233.  
  234.     register int tagi = 0;          /* tag stack index   */
  235.     register int tagc = 1;          /* actual tag count  */
  236.  
  237.     register int n;
  238.     register CHAR mask;        /* xor mask -CCL/NCL */
  239.     int c1, c2;
  240.         
  241.     if (!pat || !*pat)
  242.         if (sta)
  243.             return 0;
  244.         else
  245.             badpat("No previous regular expression");
  246.     sta = NOP;
  247.  
  248.     for (p = pat; *p; p++) {
  249.         lp = mp;
  250.         switch(*p) {
  251.  
  252.         case '.':               /* match any char..  */
  253.             store(ANY);
  254.             break;
  255.  
  256.         case '^':               /* match beginning.. */
  257.             if (p == pat)
  258.                 store(BOL);
  259.             else {
  260.                 store(CHR);
  261.                 store(*p);
  262.             }
  263.             break;
  264.  
  265.         case '$':               /* match endofline.. */
  266.             if (!*(p+1))
  267.                 store(EOL);
  268.             else {
  269.                 store(CHR);
  270.                 store(*p);
  271.             }
  272.             break;
  273.  
  274.         case '[':               /* match char class..*/
  275.             store(CCL);
  276.  
  277.             if (*++p == '^') {
  278.                 mask = 0377;    
  279.                 p++;
  280.             }
  281.             else
  282.                 mask = 0;
  283.  
  284.             if (*p == '-')        /* real dash */
  285.                 chset(*p++);
  286.             if (*p == ']')        /* real brac */
  287.                 chset(*p++);
  288.             while (*p && *p != ']') {
  289.                 if (*p == '-' && *(p+1) && *(p+1) != ']') {
  290.                     p++;
  291.                     c1 = *(p-2) + 1;
  292.                     c2 = *p++;
  293.                     while (c1 <= c2)
  294.                         chset(c1++);
  295.                 }
  296. #ifdef EXTEND
  297.                 else if (*p == '\\' && *(p+1)) {
  298.                     p++;
  299.                     chset(*p++);
  300.                 }
  301. #endif
  302.                 else
  303.                     chset(*p++);
  304.             }
  305.             if (!*p)
  306.                 badpat("Missing ]");
  307.  
  308.             for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  309.                 store(mask ^ bittab[n]);
  310.     
  311.             break;
  312.  
  313.         case '*':               /* match 0 or more.. */
  314.         case '+':               /* match 1 or more.. */
  315.             if (p == pat)
  316.                 badpat("Empty closure");
  317.             lp = sp;        /* previous opcode */
  318.             if (*lp == CLO)        /* equivalence..   */
  319.                 break;
  320.             switch(*lp) {
  321.  
  322.             case BOL:
  323.             case BOT:
  324.             case EOT:
  325.             case BOW:
  326.             case EOW:
  327.             case REF:
  328.                 badpat("Illegal closure");
  329.             default:
  330.                 break;
  331.             }
  332.  
  333.             if (*p == '+')
  334.                 for (sp = mp; lp < sp; lp++)
  335.                     store(*lp);
  336.  
  337.             store(END);
  338.             store(END);
  339.             sp = mp;
  340.             while (--mp > lp)
  341.                 *mp = mp[-1];
  342.             store(CLO);
  343.             mp = sp;
  344.             break;
  345.  
  346.         case '\\':              /* tags, backrefs .. */
  347.             switch(*++p) {
  348.  
  349.             case '(':
  350.                 if (tagc < MAXTAG) {
  351.                     tagstk[++tagi] = tagc;
  352.                     store(BOT);
  353.                     store(tagc++);
  354.                 }
  355.                 else
  356.                     badpat("Too many \\(\\) pairs");
  357.                 break;
  358.             case ')':
  359.                 if (*sp == BOT)
  360.                     badpat("Null pattern inside \\(\\)");
  361.                 if (tagi > 0) {
  362.                     store(EOT);
  363.                     store(tagstk[tagi--]);
  364.                 }
  365.                 else
  366.                     badpat("Unmatched \\)");
  367.                 break;
  368.             case '<':
  369.                 store(BOW);
  370.                 break;
  371.             case '>':
  372.                 if (*sp == BOW)
  373.                     badpat("Null pattern inside \\<\\>");
  374.                 store(EOW);
  375.                 break;
  376.             case '1':
  377.             case '2':
  378.             case '3':
  379.             case '4':
  380.             case '5':
  381.             case '6':
  382.             case '7':
  383.             case '8':
  384.             case '9':
  385.                 n = *p-'0';
  386.                 if (tagi > 0 && tagstk[tagi] == n)
  387.                     badpat("Cyclical reference");
  388.                 if (tagc > n) {
  389.                     store(REF);
  390.                     store(n);
  391.                 }
  392.                 else
  393.                     badpat("Undetermined reference");
  394.                 break;
  395. #ifdef EXTEND
  396.             case 'b':
  397.                 store(CHR);
  398.                 store('\b');
  399.                 break;
  400.             case 'n':
  401.                 store(CHR);
  402.                 store('\n');
  403.                 break;
  404.             case 'f':
  405.                 store(CHR);
  406.                 store('\f');
  407.                 break;
  408.             case 'r':
  409.                 store(CHR);
  410.                 store('\r');
  411.                 break;
  412.             case 't':
  413.                 store(CHR);
  414.                 store('\t');
  415.                 break;
  416. #endif
  417.             default:
  418.                 store(CHR);
  419.                 store(*p);
  420.             }
  421.             break;
  422.  
  423.         default :               /* an ordinary char  */
  424.             store(CHR);
  425.             store(*p);
  426.             break;
  427.         }
  428.         sp = lp;
  429.     }
  430.     if (tagi > 0)
  431.         badpat("Unmatched \\(");
  432.     store(END);
  433.     sta = OKP;
  434.     return 0;
  435. }
  436.  
  437.  
  438. static char *bol;
  439. static char *bopat[MAXTAG];
  440. static char *eopat[MAXTAG];
  441. char *pmatch();
  442.  
  443. /*
  444.  * re_exec:
  445.  *     execute nfa to find a match.
  446.  *
  447.  *    special cases: (nfa[0])    
  448.  *        BOL
  449.  *            Match only once, starting from the
  450.  *            beginning.
  451.  *        CHR
  452.  *            First locate the character without
  453.  *            calling pmatch, and if found, call
  454.  *            pmatch for the remaining string.
  455.  *        END
  456.  *            re_comp failed, poor luser did not
  457.  *            check for it. Fail fast.
  458.  *
  459.  *    If a match is found, bopat[0] and eopat[0] are set
  460.  *    to the beginning and the end of the matched fragment,
  461.  *    respectively.
  462.  *
  463.  */
  464.  
  465. int
  466. re_exec(lp)
  467. register char *lp;
  468. {
  469.     register char c;
  470.     register char *ep = 0;
  471.     register CHAR *ap = nfa;
  472.  
  473.     bol = lp;
  474.  
  475.     bopat[0] = 0;
  476.     bopat[1] = 0;
  477.     bopat[2] = 0;
  478.     bopat[3] = 0;
  479.     bopat[4] = 0;
  480.     bopat[5] = 0;
  481.     bopat[6] = 0;
  482.     bopat[7] = 0;
  483.     bopat[8] = 0;
  484.     bopat[9] = 0;
  485.  
  486.     switch(*ap) {
  487.  
  488.     case BOL:            /* anchored: match from BOL only */
  489.         ep = pmatch(lp,ap);
  490.         break;
  491.     case CHR:            /* ordinary char: locate it fast */
  492.         c = *(ap+1);
  493.         while (*lp && *lp != c)
  494.             lp++;
  495.         if (!*lp)        /* if EOS, fail, else fall thru. */
  496.             return 0;
  497.     default:            /* regular matching all the way. */
  498.         while (*lp) {
  499.             if ((ep = pmatch(lp,ap)))
  500.                 break;
  501.             lp++;
  502.         }
  503.         break;
  504.     case END:            /* munged automaton. fail always */
  505.         return 0;
  506.     }
  507.     if (!ep)
  508.         return 0;
  509.  
  510.     if (internal_error)
  511.         return -1;
  512.  
  513.     bopat[0] = lp;
  514.     eopat[0] = ep;
  515.     return 1;
  516. }
  517.  
  518. /* 
  519.  * pmatch: 
  520.  *    internal routine for the hard part
  521.  *
  522.  *     This code is mostly snarfed from an early
  523.  *     grep written by David Conroy. The backref and
  524.  *     tag stuff, and various other mods are by oZ.
  525.  *
  526.  *    special cases: (nfa[n], nfa[n+1])
  527.  *        CLO ANY
  528.  *            We KNOW ".*" will match ANYTHING
  529.  *            upto the end of line. Thus, go to
  530.  *            the end of line straight, without
  531.  *            calling pmatch recursively. As in
  532.  *            the other closure cases, the remaining
  533.  *            pattern must be matched by moving
  534.  *            backwards on the string recursively,
  535.  *            to find a match for xy (x is ".*" and 
  536.  *            y is the remaining pattern) where
  537.  *            the match satisfies the LONGEST match
  538.  *            for x followed by a match for y.
  539.  *        CLO CHR
  540.  *            We can again scan the string forward
  541.  *            for the single char without recursion, 
  542.  *            and at the point of failure, we execute 
  543.  *            the remaining nfa recursively, as
  544.  *            described above.
  545.  *
  546.  *    At the end of a successful match, bopat[n] and eopat[n]
  547.  *    are set to the beginning and end of subpatterns matched
  548.  *    by tagged expressions (n = 1 to 9).    
  549.  *
  550.  */
  551.  
  552. /*
  553.  * character classification table for word boundary
  554.  * operators BOW and EOW. the reason for not using 
  555.  * ctype macros is that we can let the user add into 
  556.  * our own table. see re_modw. This table is not in
  557.  * the bitset form, since we may wish to extend it
  558.  * in the future for other character classifications. 
  559.  *
  560.  *    TRUE for 0-9 A-Z a-z _
  561.  */
  562. static char chrtyp[MAXCHR] = {
  563.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  564.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  565.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  566.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  567.     0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 
  568.     1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 
  569.     0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 
  570.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  571.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  572.     1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 
  573.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  574.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  575.     1, 1, 1, 0, 0, 0, 0, 0
  576.     };
  577.  
  578. #define inascii(x)    (0177&(x))
  579. #define iswordc(x)     chrtyp[inascii(x)]
  580. #define isinset(x,y)     ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
  581.  
  582. /*
  583.  * skip values for CLO XXX to skip past the closure
  584.  *
  585.  */
  586.  
  587. #define ANYSKIP    2     /* [CLO] ANY END ...         */
  588. #define CHRSKIP    3    /* [CLO] CHR chr END ...     */
  589. #define CCLSKIP 18    /* [CLO] CCL 16bytes END ... */
  590.  
  591. static char *
  592. pmatch(lp, ap)
  593. register char *lp;
  594. register CHAR *ap;
  595. {
  596.     register int op, c, n;
  597.     register char *e;        /* extra pointer for CLO */
  598.     register char *bp;        /* beginning of subpat.. */
  599.     register char *ep;        /* ending of subpat..     */
  600.     char *are;            /* to save the line ptr. */
  601.  
  602.     while ((op = *ap++) != END)
  603.         switch(op) {
  604.  
  605.         case CHR:
  606.             if (*lp++ != *ap++)
  607.                 return 0;
  608.             break;
  609.         case ANY:
  610.             if (!*lp++)
  611.                 return 0;
  612.             break;
  613.         case CCL:
  614.             c = *lp++;
  615.             if (!isinset(ap,c))
  616.                 return 0;
  617.             ap += BITBLK;
  618.             break;
  619.         case BOL:
  620.             if (lp != bol)
  621.                 return 0;
  622.             break;
  623.         case EOL:
  624.             if (*lp)
  625.                 return 0;
  626.             break;
  627.         case BOT:
  628.             bopat[*ap++] = lp;
  629.             break;
  630.         case EOT:
  631.             eopat[*ap++] = lp;
  632.             break;
  633.          case BOW:
  634.             if (lp!=bol && iswordc(lp[-1]) || !iswordc(*lp))
  635.                 return 0;
  636.             break;
  637.         case EOW:
  638.             if (lp==bol || !iswordc(lp[-1]) || iswordc(*lp))
  639.                 return 0;
  640.             break;
  641.         case REF:
  642.             n = *ap++;
  643.             bp = bopat[n];
  644.             ep = eopat[n];
  645.             while (bp < ep)
  646.                 if (*bp++ != *lp++)
  647.                     return 0;
  648.             break;
  649.         case CLO:
  650.             are = lp;
  651.             switch(*ap) {
  652.  
  653.             case ANY:
  654.                 while (*lp)
  655.                     lp++;
  656.                 n = ANYSKIP;
  657.                 break;
  658.             case CHR:
  659.                 c = *(ap+1);
  660.                 while (*lp && c == *lp)
  661.                     lp++;
  662.                 n = CHRSKIP;
  663.                 break;
  664.             case CCL:
  665.                 while ((c = *lp) && isinset(ap+1,c))
  666.                     lp++;
  667.                 n = CCLSKIP;
  668.                 break;
  669.             default:
  670.                 internal_error++;
  671.                 return 0;
  672.             }
  673.  
  674.             ap += n;
  675.  
  676.             while (lp >= are) {
  677.                 if (e = pmatch(lp, ap))
  678.                     return e;
  679.                 --lp;
  680.             }
  681.             return 0;
  682.         default:
  683.             internal_error++;
  684.             return 0;
  685.         }
  686.     return lp;
  687. }
  688.